package com.linyaonan.leetcode.medium._94;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个二叉树，返回它的中序 遍历。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [1,3,2]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * @author: Lin
 * @date: 2020/1/18
 */
public class BinaryTreeInorderTraversal {
    //    List<Integer> result;
//    public List<Integer> inorderTraversal(TreeNode root) {
//        result = new ArrayList<>();
//        dfs(root);
//        return result;
//    }
//
//    private void dfs(TreeNode node) {
//        if (node != null) {
//            dfs(node.left);
//            result.add(node.val);
//            dfs(node.right);
//        }
//    }

    List<Integer> result;

    public List<Integer> inorderTraversal(TreeNode root) {
        result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !s.isEmpty()) {
            while (curr != null) {
                s.push(curr);
                curr = curr.left;
            }
            curr = s.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }
}
